class Solution(object):
    # 双指针
    def maxArea(self, height):  # O(n)
        """
        :type height: List[int] of non-negative integers
            len(height) >= 2
        :rtype: int
        """
        if len(height) == 2:
            return min(height)
        
        # 尽量不使用 Recursion
        # left = 0
        # right = len(height) - 1
        # h = min(height[left], height[right])
        # # h = height[left] if height[left] < height[right] else height[right]
        # w = right - left
        
        # return max(h * w, self.maxArea(height[1:]) \
        #                   if height[left] < height[right] \
        #                   else self.maxArea(height[:-1]))
        
        # 尽量使用 Iteration
        left = 0
        right = len(height) - 1
        s = 0
        while right - left >= 1:
            h = min(height[left], height[right])
            s = max(s, h * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return s


if __name__ == "__main__":
    soln = Solution()
    print(soln.maxArea([1,2,1]))
    print(soln.maxArea([1,2,3]))
    print(soln.maxArea([1,8,6,2,5,4,8,3,7]))
    print(soln.maxArea([4,3,2,1,4]))
